1. Technical Field
The present invention relates to a method of searching a neighboring cell address in a same resolution octree structure, more specifically to a method of quickly and simply address searching values of neighboring cells having same sizes (or resolutions) about a selected cell in an octree structure.
2. Description of the Related Art
For a basic understanding of the subject matter of the present invention, reference is hereby made to the terms Data Structure, Programming Language and Computer as defined by The Wikipedia Encyclopedia, definitions of which are hereby incorporated by reference.
Typically, an octree is one of the tree data structures that are popular due to easy and simple use.
As shown in FIG. 1, the typical octree structure gives an address by assigning zero and positive integers of 1 through 7 from a lower left rear corner before performing the encoding. The typical octree structure is usable for any data that can be represented in the form of having 3 orthogonal axes. Accordingly, the typical octree structure can be used in the fields of computer graphics, computer vision, and robotics, which represent database data in a space having 3 orthogonal axes or which represent an actual circumstance based on a reference point by using 3 orthogonal axes.
Especially, in the database field, the octree structure is used when the clustering is used based on the grid. The octree structure is also used in the fields of graphics or vision when an object in the 3-dimensional space is rendered or modeled.
Many studies follow the octree structure, and especially, many efforts are made to search neighboring cells.
It is very important to find out the neighborship between generated cells in the octree structure in order to group data. Moreover, recognizing the neighborship is very important for the probable modeling of a 3-dimensional object in the fields of computer vision and robotics and studies on job circumstances.
For example, the octree structure is very useful to a factor constituting one object by using the connection of a plurality of scattered cells having various resolutions that in the modeling field. The octree structure can be also efficiently used by searching a free space for a robot in a work space considering movement to plan a path for avoidance or working and to generate a map.
On the other hand, the work space modeling and the planning of available paths or motions has very important effects on the performance of a robot in driving and manipulating of the robot. In other words, it should be firstly considered how fast a plan for available paths or motions is made.
In the case of the field of robots that projects and uses a 3-dimensional space, however, there always have been inherent errors of 3-dimensional points and there may be uncompleted data having forms that can not be recognized. The method of addresses of neighboring cells in the octree structure is mainly used to overcome the problems in analyzing a space in the 3-dimensional space having errors.
Information related to octree cells is very important in the process of searching the addresses of the neighboring cells. It is because one cell can become a 3-dimensional space and the cell can include a variety of information. Accordingly, it is required to recognize the neighborship between all or some of cells in order to plan a path or define an object and to be used for the studies to understand the space.
Thus, it becomes important to study how the cells are searched, where the cells are located, and how the cells are connected to each other. However, it should be firstly considered to search the neighborship of a selected cell.
According to the typical method of searching an address of a neighboring cell suggested by H. Samet [The Design and Analysis of Spatial Data Structures Reading, Mass.: Addison-Wesley, 1990.], which is incorporated by reference in its entirety herein, the address value of the neighboring cell is computed in the circumstance having a direction for a pointer octree and a common ancestor is searched before an algorithm starts.
This method can analyze a tree structure until a common ancestor is found, but the method has no solution when there is no neighboring cell. This algorithm is re-studied by J. E. Besanon [J. E. Besangon, Vision par Ordinateur en Deux et Trois Dimensions. Paris, France: Eyrolles, 1988, pp. 341-353]. The method of encoding an octree address is additionally studied.
Then, the backtracking method in the octree structure, which is suggested by D. H. Ballard and C. M. Brown [D. H. Ballard and C. M. Brown, Computer Vision. Englewood Cliffs, N.J.: Prentice-Hall, 1982], which is incorporated by reference in its entirety herein, back-tracks the generation process of the octree structure to the common parent. In the tree structure and design, this backtracking method is used for two selected cells. However, this method has no solution when two cells are in contact by the corner with each other.